public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {100,4,3,5,1,8,2,7,6,9,10};
        selectSort(arr);
        for(int i : arr) {
            System.out.print(i + " ");
        }
    }


    /**
     * 选择排序
     * 时间复杂度：O(n^2) 不管你本身的数据 是有序还是无序  都是这个复杂度
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param arr
     */
    //双指针，同时寻找最大值最小值
    private static void selectSort(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int maxindex = right;
            int minindex = left;

            for(int i = left; i < right; i++) {
                if(arr[i] < arr[minindex]) {
                    minindex = i;
                }
                if (arr[i] > arr[maxindex]) {
                    maxindex = i;
                }
            }
            Swap(arr, minindex, left);
            if (maxindex == left) {
                maxindex = minindex;
            }
            Swap(arr, maxindex, right);

            right--;
            left++;
        }
    }

//    //单指针，寻找最小值
//    private static void selectSort(int[] arr) {
//        for (int i = 0; i < arr.length; i ++) {
//            int min = i;
//            for (int j = i + 1; j < arr.length; j++) {
//                if (arr[j] > arr[min]) {
//                    min = j;
//                }
//            }
//            Swap(arr, i, min);
//        }
//    }

    private static void Swap(int[]arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
